Section: New Results

Discrete and computational geometry

On Point-sets that Support Planar Graphs

A set of points is said universal if it supports a crossing-free drawing of any planar graph. For a planar graph with $n$ vertices, if bends on edges of the drawing are permitted, universal point-sets of size $n$ are known, but only if the bend-points are in arbitrary positions. If the locations of the bend-points must also be specified as part of the point-set, no result was known, and we prove that any planar graph with $n$ vertices can be drawn on a universal set $𝒮$ of $O(n^2/logn)$ points with at most one bend per edge and with the vertices and the bend points in $𝒮$. If two bends per edge are allowed, we show that $O(nlogn)$ points are sufficient, and if three bends per edge are allowed, $\Theta \left(n\right)$ points are sufficient. When no bends on edges are permitted, no universal point-set of size $o\left(n^2\right)$ is known for the class of planar graphs. We show that a set of $n$ points in balanced biconvex position supports the class of maximum-degree-3 series-parallel lattices [20] .

Helly numbers of acyclic families

The nerve of a family of sets is a simplicial complex that records the intersection pattern of its subfamilies. Nerves are widely used in computational geometry and topology, because the nerve theorem guarantees that the nerve of a family of geometric objects has the same topology as the union of the objects, if they form a good cover.

We relaxed the good cover assumption to the case where each subfamily intersects in a disjoint union of possibly several homology cells, and we proved a generalization of the nerve theorem in this framework, using spectral sequences from algebraic topology. We then deduced a new topological Helly-type theorem that unifies previous results of Amenta, Kalai and Meshulam, and Matoušek. This Helly-type theorem is applied to (re)prove, in a unified way, bounds on Helly numbers of sets of lines in geometric transversal theory [25] .